package com.datastructure.test.isbalancebinarytree;

public class IsBalanceBinaryTree {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left= new TreeNode(2);
        root.right=new TreeNode(3);
        root.right.right=new TreeNode(4);
        root.right.right.right=new TreeNode(5);
        IsBalanceBinaryTree isBalanceBinaryTree = new IsBalanceBinaryTree();
        boolean isBalanced_solution = isBalanceBinaryTree.IsBalanced_Solution(root);
        System.out.println(isBalanced_solution);
    }

    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null){
            return true;
        }
        return getIsBalanced_Solution(root);
    }

    public boolean getIsBalanced_Solution(TreeNode root) {
        if(root==null){
            return true;
        }
        int leftDepth = root.left!=null?getTreeDepth(root.left):0;
        int rightDepth = root.right!=null?getTreeDepth(root.right):0;
        return Math.abs(leftDepth-rightDepth)<=1&&getIsBalanced_Solution(root.left)
                &&getIsBalanced_Solution(root.right);
    }

    public int getTreeDepth(TreeNode root){
        if(root==null){
            return 0;
        }
        int max = 0;
        if(root.left!=null){
            max = Math.max(max,getTreeDepth(root.left));
        }
        if(root.right!=null){
            max = Math.max(max,getTreeDepth(root.right));
        }
        return max+1;
    }

    public boolean IsBalanced_Solution1(TreeNode root) {
        // 空树也是平衡二叉树
        if(root == null) {
            return true;
        }
        return getHeight(root) != -1;
    }

    public int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        // 递归计算当前root左右子树的高度差
        int left = getHeight(root.left);
        // 当前节点左子树不平衡,则该树不平衡，相当于可行性剪枝，没必要遍历所有节点
        if(left < 0) {
            return -1;
        }
        int right = getHeight(root.right);
        if(right < 0) {
            return -1;
        }
        // 自底向顶，每次+1，不断计算高度，直到递归到某个节点使得左右子树高度差大于1，则返回-1表示不平衡
        // 左右子树中高度较高的, 作为当前节点的高度, 用于向上递归判断是否平衡
        return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }
}
